﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TSP
{
    class TSPSolverGreedy : ITSPSolver
    {
        private class Node
        {
            private City city;
            private bool isIncluded;

            public Node(City city)
            {
                this.city = city;
                isIncluded = false;
            }

            public City City
            {
                get { return city; }
            }

            public bool IsIncluded
            {
                get { return isIncluded; }
                set { isIncluded = value; }
            }
        }

        private class Edge
        {
            private Node start;
            private Node end;
            private double cost;

            public Edge(Node start, Node end)
            {
                this.start = start;
                this.end = end;

                cost = start.City.costToGetTo(end.City);
            }

            public Node Start
            {
                get { return start; }
            }

            public Node End
            {
                get { return end; }
            }

            public double Cost
            {
                get { return cost; }
            }
        }

        private Edge[,] adjacencyMatrix;

        private void buildAdjacencyMatrix(City[] input)
        {
            Node[] nodes = new Node[input.Length];
            for (int i = 0; i < input.Length; ++i)
                nodes[i] = new Node(input[i]);

            adjacencyMatrix = new Edge[input.Length, input.Length];

            for (int i = 0; i < input.Length; ++i)
            {
                for (int j = 0; j < input.Length; ++j)
                {
                    adjacencyMatrix[i, j] = new Edge(nodes[i], nodes[j]);
                }
            }
        }

        private int findSmallestCost()
        {
            double cost = double.MaxValue;
            int result = -1;

            for (int i = 0; i < adjacencyMatrix.GetLength(0); ++i)
            {
                for (int j = 0; j < adjacencyMatrix.GetLength(1); ++j)
                {
                    if (adjacencyMatrix[i, j].Cost < cost)
                    {
                        cost = adjacencyMatrix[i, j].Cost;
                        result = i;
                    }
                }
            }

            return result;
        }

        private int getNextCity(int startCity)
        {
            double cost = double.MaxValue;
            int result = -1;

            for (int i = 0; i < adjacencyMatrix.GetLength(0); ++i)
            {
                if (!adjacencyMatrix[startCity,i].End.IsIncluded && adjacencyMatrix[startCity, i].Cost < cost)
                {
                    cost = adjacencyMatrix[startCity, i].Cost;
                    result = i;
                }
            }

            return result;
        }

        public List<City> solveProblem(City[] input)
        {
            buildAdjacencyMatrix(input);

            int currentCity = findSmallestCost();

            List<City> result = new List<City>(input.Length);

            for (int i = 0; i < input.Length; ++i)
            {
                result.Add(input[currentCity]);
                adjacencyMatrix[currentCity, currentCity].Start.IsIncluded = true;
                currentCity = getNextCity(currentCity);
            }

            return result;
        }
    }
}
